class Solution {
public:
    vector<int> cache;                                   
    int n;
    int dfs(vector<string>& ans,int state,string& tar){
        if(cache[state] != 0) return cache[state];
        if(((1 << n) - 1) == state) return 0;
        int ret = 50;
        for(string& s : ans){
            int newState = state;
            for(char& c : s){
                for(int i = 0;i < n;i++){
                    if(c == tar[i] && ((newState >> i) & 1) == 0){
                        newState |= (1 << i);
                        break;
                    }
                }
            }
            if(newState != state){
                ret = min(ret,dfs(ans,newState,tar)+1);
            }
        }
        cache[state] = ret;
        return cache[state];
    }
                                        
    int minStickers(vector<string>& stickers, string target) {
       int m = 1 << 15;
       n = target.size();
       cache.resize(m,0);
       int ret = dfs(stickers,0,target);
       return ret == 50 ? -1 : ret;
    }
};
